package com.zhang.hashtable;

import java.util.Arrays;

/**
 * @author zhang
 * @time 2022/03/19 15:57:03
 */
public class HashMapLinearProbing {
    private class Entry {
        private int key;
        private String value;

        public Entry(int key, String value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return value;
        }
    }

    private Entry[] entries = new Entry[5];
    private int count;

    public void put(int key, String value) {
        Entry entry = getEntry(key);
        if (entry != null) {
            entry.value = value;
            return;
        }
        if (isFull()) {
            throw new IllegalStateException();
        }

        entries[getIndex(key)] = new Entry(key, value);
        count++;

    }
    private Entry getEntry(int key) {
        int index = getIndex(key);
        //这里如果直接走后面的null,表明已经满了，在put时会被抛异常的
        return index >= 0 ? entries[index] : null;
    }

    public void remove(int key) {
        int index = getIndex(key);
        if (index == -1 || entries[index] == null) {
            return;
        }
        entries[index] = null;
        count--;
    }

    public String get(int key) {
        Entry entry = getEntry(key);
        return (entry != null) ? entry.value : entry.value;
    }

    private int index(int key, int i) {
        return (hash(key) + i) % entries.length;
    }

    private int getIndex(int key) {
        int steps = 0;

        while (steps < entries.length) {
            int index = index(key, steps++);
            Entry entry = entries[index];
            if (entry == null || entry.key == key) {
                return index;
            }
        }
        return -1;


    }


    private int hash(int key) {
        return key % entries.length;
    }
    private boolean isFull() {
        return count == entries.length;
    }

    @Override
    public String toString() {
        return Arrays.toString(entries);
    }
}
